package top.minuy.structure.graph.matching;

import top.minuy.res.graph.GraphRes;
import top.minuy.structure.graph.representations.table.Graph;

/**
 * @author Minuy
 * @time 21:38
 * @date 2021/11/29
 */
public class Test {
    public static void main(String[] args) {
        System.out.println("二分图最大流最大匹配算法：");
        System.out.println("测试1：");
        test(GraphRes.G_MAX_FLOW_MATCHING_01);
        System.out.println("测试2：");
        test(GraphRes.G_MAX_FLOW_MATCHING_02);

        System.out.println("二分图匈牙利最大匹配算法（广度优先遍历）：");
        System.out.println("测试1：");
        testH(GraphRes.G_MAX_FLOW_MATCHING_01);
        System.out.println("测试2：");
        testH(GraphRes.G_MAX_FLOW_MATCHING_02);

        System.out.println("二分图匈牙利最大匹配算法（深度优先遍历）：");
        System.out.println("测试1：");
        testHh(GraphRes.G_MAX_FLOW_MATCHING_01);
        System.out.println("测试2：");
        testHh(GraphRes.G_MAX_FLOW_MATCHING_02);
    }

    private static void test(String path) {
        Graph g1 = new Graph(path);
        BipartiteMatching bm1 = new BipartiteMatching(g1);
        System.out.println(String.format(
                "完全匹配：%s，最大匹配：%d。", bm1.isPerfectMatching(), bm1.maxMatching()));
    }

    private static void testH(String path) {
        Graph g = new Graph(path);
        Hungarian hungarian = new Hungarian(g);
        System.out.println(String.format(
                "完全匹配：%s，最大匹配：%d。",
                hungarian.isPerfectMatching(), hungarian.maxMatching()));
        for (int v=0;v<g.V();v++){
            System.out.println(
                    String.format("%d <-> %d", v,hungarian.matching(v)));
        }
    }

    private static void testHh(String path) {
        Graph g = new Graph(path);
        HungarianDFS hungarian = new HungarianDFS(g);
        System.out.println(String.format(
                "完全匹配：%s，最大匹配：%d。",
                hungarian.isPerfectMatching(), hungarian.maxMatching()));
        for (int v=0;v<g.V();v++){
            System.out.println(
                    String.format("%d <-> %d", v,hungarian.matching(v)));
        }
    }
}
